吴师兄学算法

# LeetCode 90、子集II

# 一、题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {

        // 先排序，这样才能对比当前元素和之前元素是否相同
        Arrays.sort(nums);

        // 结果集合
        List<List<Integer>> sets = new ArrayList<List<Integer>>();

        // 每次的子集
        List<Integer> subset = new ArrayList<Integer>();

        // 执行回溯算法
        backtrack( 0 , nums , subset , sets);

        // 返回结果
        return sets;

    }

    // i 表示递归时正在访问的数组元素下标
    // nums 表示当前集合中的元素
    // subset 表示每次递归后生成的子集
    // sets 表示最终生成的所有子集合
    private void backtrack( int i , int[] nums , List<Integer> subset , List<List<Integer>> sets ){

        // 每次确定好一个子集，都把它加入到结果集合中
        sets.add(new ArrayList<Integer>(subset));

        // 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        // 本题中可以不加这个判断，大家可以思考一下为什么可以不加，结合 for 循环的边界来思考
        if( i >= nums.length){
            return;
        }

        for( int j = i ; j < nums.length ; j++ ){

            // 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            if( j > i && nums[j] == nums[ j - 1 ]) continue;

            // 把本次递归访问的元素加入到 subset 数组中
            subset.add(nums[j]);

            // 5、做出选择，递归调用该函数，进入下一层继续搜索
            // 递归
            backtrack( j + 1 , nums , subset , sets);

            // 6、撤销选择，回到上一层的状态
            // 取消对 nums[i] 的选择
            subset.remove(subset.size() - 1);

        }

    }
}

Python

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        """
        :param nums: List[int]
        :return: List[List[int]]
        """
        # 先排序，这样才能对比当前元素和之前元素是否相同
        nums.sort()
        
        # 结果集合
        sets = []

        # 每次的子集
        subset = []

        # 执行回溯算法
        self.backtrack(0, nums, subset, sets)

        # 返回结果
        return sets

    def backtrack(self, i, nums, subset, sets):
        """
        :param i: int
        :param nums: List[int]
        :param subset: List[int]
        :param sets: List[List[int]]
        """
        # 每次确定好一个子集，都把它加入到结果集合中
        sets.append(subset[:])

        # 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        # 本题中可以不加这个判断，大家可以思考一下为什么可以不加，结合 for 循环的边界来思考
        if i >= len(nums):
            return

        for j in range(i, len(nums)):

            # 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            if j > i and nums[j] == nums[j - 1]:
                continue

            # 把本次递归访问的元素加入到 subset 数组中
            subset.append(nums[j])

            # 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            

            # 5、做出选择，递归调用该函数，进入下一层继续搜索
            # 递归
            self.backtrack(j + 1, nums, subset, sets)

            # 6、撤销选择，回到上一层的状态
            # 取消对 nums[i] 的选择
            subset.pop()

# 四、复杂度分析

时间复杂度：O(n * 2 ^ n)。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。

空间复杂度：O(n)。临时数组 subsets 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

← LeetCode 78、子集 →